package year2023.greedy;

import java.util.*;

public class Code01_LowestLexicography {

    //贪心算法
    /*
    * 1.最自然智慧的算法
    * 2.用一种局部最功利的标准，总是做出在当前看来是最好的选择
    * 3.难点在于证明局部最功利的标准可以得到全局最优解
    * 4.对于贪心算法的学习，主要以增加阅历和经验为主
    */

    //给定一个由字符串组成的数组strs
    //必须把所有的字符串拼接起来
    //返回所有可能的拼接结果中，字典序最小的结果

    //暴力解
    public static String lowestString1(String[] strs){
        if (strs == null || strs.length == 0){
            return "";
        }
        TreeSet<String> ans = process(strs);
        return ans.first();

    }

    //strs中所有字符串全排列，返回所有可能的结果
    public static TreeSet<String> process(String[] strs){
        TreeSet<String> ans = new TreeSet<>();
        if (strs.length == 0){
            ans.add("");
            return ans;
        }
        for (int i = 0; i < strs.length; i++) {
            String first = strs[i];
            String[] nexts = removeIndexString(strs, i);
            TreeSet<String> next = process(nexts);
            for (String cur : next){
                ans.add(first + cur);
            }
        }
        return ans;
    }

    //{"abc" , "cks" , "bct"}
    //   0       1       2
    // removeIndexString(arr , 1) -> {"abc","bct"}
    public static String[] removeIndexString(String[] arr, int index){
        int N = arr.length;
        String[] ans = new String[N-1];
        int ansIndex = 0;
        for (int i = 0; i < N; i++) {
            if (i != index){
                ans[ansIndex++] = arr[i];
            }
        }
        return ans;
    }

    public static class MyComparator implements Comparator<String>{

        @Override
        public int compare(String a, String b){
            return (a + b).compareTo(b + a);
        }
    }

    public static String lowestString2(String[] strs){
        if (strs == null || strs.length == 0){
            return "";
        }
        Arrays.sort(strs, new MyComparator());
        String res = "";
        for (int i = 0; i < strs.length; i++) {
            res += strs[i];
        }
        return res;
    }

    public static void main(String[] args) {
        String[] test = {"b","ba"};
        System.out.println(lowestString2(test));
    }

}
